package LeetCode_力扣;
//142. 环形链表 II
//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

/**
 * 思路：假设环形节点前的路径为 a;环形入口的节点 到 快慢指针在环内相交时的节点距离为 b
 * 环形内剩下的距离为 c。
 * 那么快指针的路径为 a + N(b + c) + b;（N表示走了N圈）
 * 那么慢指针的路径为 a + b;(因为慢指针在进入环的时候走一半就肯定会被快指针追上)
 * 快指针的路径是慢的两倍：  a + N(b + c) + b = 2(a + b);
 * 化简一下： N(b + c) = a + b，再化简一下，从N里面提出一个 b + c；
 *   等于 (N - 1)(b + c) + c = a;
 * 重点来了！：(N - 1)(b + c)这个只是表示圈数，当一个指针从头节点开始走，
 * 慢指针从b点上开始走，当两个指针相遇时，必然是入口节点。
 * 因为 (N - 1)(b + c) + c = a; 路径是相等的。不懂的话你可以先
 * 假设 如果 N == 1的话 a = c
 */


/*

public class detectCycle_142 {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;//慢指针
        ListNode fast = head;//快指针

        while(fast != null && fast.next != null){

            slow = slow.next;
            fast = fast.next.next;
            //某一刻路过时
            if(slow == fast){
                //此时创建一个新指针让它从头走
                ListNode prve = head;
                while(prve != slow){
                    prve = prve.next;
                    slow = slow.next;
                }//循环完后就相遇了
                return prve;
            }
        }

        return null;
    }
}

 */








//class ListNode {
//    int val;
//    ListNode next;
//
//    ListNode(int x) {
//        val = x;
//        next = null;
//    }
//}
